// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-08 18:56
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;

public class BuildTreePI {
    /**
     * 根据二叉树的前序和中序遍历进行排序
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 二叉树的前序遍历序列是根左右，中序遍历序列是左根右-> 可以根据两个遍历序列定位树的根节点
        // 根据树的根节点和中序遍历序列可以确定树的左右节点
        return constructTreeByPreAndIn(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode constructTreeByPreAndIn(int[] preorder, int[] inorder, int start, int end, int iStart, int iEnd) {
        if (start > end || iStart > iEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[start]);
        // 获取根节点在中序遍历序列的下标
        int index = find(preorder[start], inorder);
        int leftLen = index - iStart;
        root.left = constructTreeByPreAndIn(preorder, inorder, start + 1, start + leftLen, iStart, iStart + leftLen - 1);
        root.right = constructTreeByPreAndIn(preorder, inorder, start + leftLen + 1, end, iStart + leftLen + 1, iEnd);
        return root;
    }

    /**
     * 获取根节点在中序遍历序列中的位置
     *
     * @param val     根节点
     * @param inorder 中序遍历
     * @return 返回根节点在中序遍历的索引
     */
    private int find(int val, int[] inorder) {
        int n = inorder.length;
        for (int i = 0; i < n; i++) {
            if (val == inorder[i]) {
                return i;
            }
        }
        return -1;
    }
}
